//
//  main.cpp
//  ALG
//
//  Created by Chenxuhun on 17/4/17.
//  Copyright © 2017年 Chenxuhun. All rights reserved.
//

#include <iostream>
#include "SortTestTool.h"

template <typename T>

//选择排序
void SelectionSort(T arry[],int n){
    
    //寻找[i n）中最小的值
    for (int i = 0 ; i < n; i++) {
        
        int minIndex = i;
        for (int j = i+1; j<n; j++) {
            
            if (arry[minIndex]>arry[j]) {
                minIndex = j;
            }
        }
        std::swap(arry[i], arry[minIndex]);
    }
}


template <typename T>

//插入排序
void insertionSort(T arry[],int n){
    
    //寻找合适的插入位置
    SortTestTool::printArray(arry, n);
    for (int i = 1 ; i < n; i++) {
        
        T temp = arry[i];
        for (int j = i; j>0; j--) {
            if (arry[j-1]>temp) {
                arry[j] = arry[j-1];
            }else{
               arry[j] = temp;
               break;
            }
        }
        SortTestTool::printArray(arry, n);
    }
}

template <typename T>
void maoPaoSort(T arry[],int n){
    
    SortTestTool::printArray(arry, n);
    for (int i = 1 ; i < n; i++) {
        
        for (int j = 0; j<n-i; j++) {
            
            if (arry[j]>arry[j+1]) {
                
                std::swap(arry[j], arry[j+1]);
            }
            
        }
         SortTestTool::printArray(arry, n);
        
    }
}



int main(int argc, const char * argv[]) {
    // insert code here...
    int n = 10;
    
    //近乎有序的数组 排序时  插入排序 排序速度很快  有时比nlog^n还要快 插入排序有真实的使用场景，比如 日志排序
    int *array = SortTestTool::generateRandomArray(n, 1, 10);
    
    int *temp = SortTestTool::copyArray(array, n);
    int *temp2 = SortTestTool::copyArray(array, n);
    
    SortTestTool::testSort("insert sort", insertionSort, array, n);
    SortTestTool::testSort("select sort", SelectionSort, temp, n);
    SortTestTool::testSort("bubble sort", maoPaoSort, temp2, n);
    delete []array;
    delete []temp;
    delete []temp2;
    return 0;
}
